package com.practice.niuke.new_direct_basics.class13;

/**
 * (1)Morris遍历
 * 一种遍历二叉树的方式， 并且时间复杂度O(N)， 额外空间复杂度O(1)
 * 通过利用原树中大量空闲指针的方式， 达到节省空间的目的
 *
 * (2)先序、 中序可以由morris遍历加工得到
 * 后序遍历也可由morris遍历加工得到， 但是把处理时机放在， 能够达到两次的节点并且是第二次
 * 到达的时候。
 *
 * (3)morris遍历的应用：怎么判断一棵树是搜索二叉树
 */
public class Code01_MorrisTraversal {

    public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 二叉树先/中/后序遍历的基本结构
     *
     * @param head head
     */
    public static void process(Node head) {
        if (head == null) {
            return;
        }
        // 1 打印时机放在第一个位置，先序遍历
        // 1
        process(head.left);
        //2 打印时机放在第二个位置，中需序历
        // 2
        process(head.right);
        // 3 打印时机放在第三个位置，后需序历
        // 3
    }


    /**
     * 一棵树的Morris序(Morris遍历算法原型)
     *
     * @param head head
     */
    public static void morris(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) { // 过流程
            // 在这个加打印行为，就是打印Morris序，System.out.println("打印"+ cur);
            // System.out.println("打印"+ cur);
            mostRight = cur.left; // mostRight是cur左孩子
            if (mostRight != null) { // cur节点有左子树（左孩子）
                // mostRight来到cur左子树的最右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) { // 这是第一次来到cur
                    // 让mostRight的右指针，指向cur节点
                    mostRight.right = cur;
                    // cur向左孩子节点移动
                    cur = cur.left;
                    continue;
                } else { // else也就是mostRight.right == cur，说明是第二次来到cur
                    // 让mostRight的右指针，指向null
                    mostRight.right = null;
                }
            }
            // cur节点没有左子树（左孩子），cur向右孩子节点移动
            cur = cur.right;
        }
    }

    /**
     * “Mossis遍历算法原型”实现先序遍历：
     * 在进行Morris遍历时，确定是第一次来到cur节点时，就打印cur节点。
     *
     * @param head head
     */
    public static void morrisPre(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) { // 过流程
            mostRight = cur.left; // mostRight是cur左孩子
            if (mostRight != null) { // cur有左子树，该节点会经过两次
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) { // 这是第一次来到cur（第一次经过该节点）
                    // 确定是第一次来到cur节点时，打印cur节点
                    System.out.println(cur.value);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // mostRight.right == cur
                    mostRight.right = null;
                }
            } else { // cur没有左子树的情况，当前不会经过两次的节点，那么现在就是第一次经过，直接打印。
                System.out.println(cur.value);
            }
            cur = cur.right;
        }
    }

    /**
     * “Mossis遍历算法原型”实现中序遍历：
     * 在进行Morris遍历时，确定一个节点只能进过一次，那么直接打印这个节点；
     * 确定一个节点能经过两次，那么第二次经过这个节点时打印这个节点。
     *
     * @param head head
     */
    public static void morrisIn(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) { // 过流程
            mostRight = cur.left; // mostRight是cur左孩子
            if (mostRight != null) { // cur有左子树，必然会经过两次
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) { // 这是第一次来到cur
                    mostRight.right = cur;
                    cur = cur.left;
                    // 回到while循环判断，不会走下面的打印逻辑，也就是第一次来到cur时，不会打印
                    continue;
                } else { // mostRight.right == cur，第二次来到cur
                    // 将mostRight.right设置为null后，会跳出外面那个大的if结构，然后打印cur节点就行。
                    mostRight.right = null;
                }
            }
            // cur没有左子树，只会经过该节点一次
            System.out.println(cur.value);
            cur = cur.right;
        }
    }

    /**
     * “Mossis遍历算法原型”实现后序遍历：
     * （1）遍历阶段：
     * （a）只“处理”能经过两地的节点，并且把“处理”时机放在第二次经过这个节点的时候；
     * 如果一个节点只能经过一次，那么它没有“处理”时机。
     * （b）“处理”过程：逆序打印 该节点的 左子树的 右边界（类似于单链表的逆序过程）
     * （2）遍历阶段完成后：
     * 单独打印 整棵树的 右边界（类似于单链表的逆序过程）。
     *
     * @param head head
     */
    public static void morrisPos(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // cur有左子树，必然会经过两次
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {// 这是第一次来到cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {// mostRight.right == cur，第二次来到cur
                    mostRight.right = null;
                    // Morris遍历过程中，唯一的处理时机（对于可以经过两次的节点，在第二次经过时打印它左子树的右边界）
                    printEdge(cur.left);
                }
            }
            cur = cur.right;
        }
        // Morris遍历完成后，打印整棵树的右边界
        printEdge(head);
        System.out.println();
    }

    /**
     * 以X为头的树，逆序打印这棵树的右边界
     *
     * @param X X
     */
    public static void printEdge(Node X) {
        // 逆序，把尾部返回（逆序后的头）
        Node tail = reverseEdge(X);
        // 顺着尾巴打印
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        // 在逆序回来
        reverseEdge(tail);
    }

    /**
     * 类似于单链表的逆序过程，改变（一棵以from为头的树的右边界中的节点的）右指针的走向。
     * （从from开始，只关心right指针，并且认为right指针就是单链表的next指针，请把这个单链表逆序）
     *
     * @param from from
     * @return Node
     */
    public static Node reverseEdge(Node from) {
        Node pre = null;
        Node next = null;
        while (from != null) {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }

    // for test -- print tree
    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    /**
     * morris遍历的应用：怎么判断一棵树是搜索二叉树
     *
     * @param head head
     * @return
     */
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        Node cur = head;
        Node mostRight = null;
        int preValue = Integer.MIN_VALUE;
        while (cur != null) { // 过流程
            mostRight = cur.left; // mostRight是cur左孩子
            if (mostRight != null) { // 有左子树
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) { // 这是第一次来到cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // mostRight.right == cur
                    mostRight.right = null;
                }
            }
            if (cur.value <= preValue) {
                return false;
            }
            preValue = cur.value;
            cur = cur.right;
        }
        return true;
    }


    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
        printTree(head);
        morrisIn(head);
        morrisPre(head);
        morrisPos(head);
        printTree(head);

    }

}
